#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 常用模数
const int MOD197 = 1e9 + 7;
const int MOD353 = 998244353;

// 返回 x 在 MOD 下的代表元
template <int MOD>
int elem(int x)
{
    return ((x % MOD) + MOD) % MOD;
}

// 快速幂
template <class T>
T fpow(T a, int b)
{
    if (a == 0)
        return 0;
    T res = 1;
    for (; b; b >>= 1, a *= a)
    {
        if (b & 1)
        {
            res *= a;
        }
    }
    return res;
}

// 模数
template <int MOD>
struct MN
{
    int x;
    MN(int x = 0) : x(elem<MOD>(x)) {}
    int val() const
    {
        return x;
    }
    MN operator-() const
    {
        return MN(-x);
    }
    MN operator~() const
    {
        return fpow(*this, MOD - 2);
    }
    MN &operator*=(const MN &rhs)
    {
        x = ll(x) * rhs.x % MOD;
        return *this;
    }
    MN &operator+=(const MN &rhs)
    {
        x = elem<MOD>(x + rhs.x);
        return *this;
    }
    MN &operator-=(const MN &rhs)
    {
        x = elem<MOD>(x - rhs.x);
        return *this;
    }
    MN &operator/=(const MN &rhs)
    {
        return *this *= ~rhs;
    }
    friend MN operator*(const MN &lhs, const MN &rhs)
    {
        MN res = lhs;
        res *= rhs;
        return res;
    }
    friend MN operator+(const MN &lhs, const MN &rhs)
    {
        MN res = lhs;
        res += rhs;
        return res;
    }
    friend MN operator-(const MN &lhs, const MN &rhs)
    {
        MN res = lhs;
        res -= rhs;
        return res;
    }
    friend MN operator/(const MN &lhs, const MN &rhs)
    {
        MN res = lhs;
        res /= rhs;
        return res;
    }
};
